Communication-Avoiding Parallel Algorithms for Solving Triangular Systems of Linear Equations

摘要

We present a new parallel algorithm for solving triangular systems withmultiple right hand sides (TRSM). TRSM is used extensively in numerical linearalgebra computations, both to solve triangular linear systems of equations aswell as to compute factorizations with triangular matrices, such as Cholesky,LU, and QR. Our algorithm achieves better theoretical scalability than knownalternatives, while maintaining numerical stability, via selective use oftriangular matrix inversion. We leverage the fact that triangular inversion andmatrix multiplication are more parallelizable than the standard TRSM algorithm.By only inverting triangular blocks along the diagonal of the initial matrix,we generalize the usual way of TRSM computation and the full matrix inversionapproach. This flexibility leads to an efficient algorithm for any ratio of thenumber of right hand sides to the triangular matrix dimension. We provide adetailed communication cost analysis for our algorithm as well as for therecursive triangular matrix inversion. This cost analysis makes it possible todetermine optimal block sizes and processor grids a priori. Relative to thebest known algorithms for TRSM, our approach can require asymptotically fewermessages, while performing optimal amounts of computation and communication interms of words sent.